package 动态规划;

public class Leedcode70爬楼梯 {

    public static void main(String[] args) {
        System.out.println(climbStairs2(3));

    }


    public static int climbStairs2(int n) {
        //base case
        int[] arr = new int[n + 1];
        arr[0] = 1;
        arr[0] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }



    /**
     * 传入台阶数，就可以按照规则求出一共有多少解决方案
     *
     * @param n 几节台阶
     * @return
     */

    public static int climbStairs1(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        //存在两个以上
        return climbStairs1(n - 1) + climbStairs1(n - 2);
    }


}
